/**
 * @author LKQ
 * @date 2022/2/21 23:02
 * @description 插入排序，时间复杂度为O(n^2)
 */
public class FormalSolution {
    public static void main(String[] args) {
        FormalSolution solution = new FormalSolution();
        ListNode root = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        solution.insertionSortList(root);
    }
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            // 头节点为空，没有数据需要插入
            return head;
        }
        // 创建虚拟节点
        ListNode dummyHead = new ListNode(0, head);
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }

}
